#include "graph.h"
#include "utils.h"
#include <algorithm>
#include <iostream>
#include <assert.h>

using namespace std;

Tree::Tree(int dep = 25) {
	this->dep = dep;
	root = new TNode();
}

/**
 * 寻找 Node 但不创建 TNode 与 Node 节点
 */
Node* Tree::findNodeNoCreate(const string s) {
	TNode **node = &root;
	int i = 0, len = s.length();
	assert(len-- == dep);
	while (i < len && *node != NULL) {
		node = (TNode **) ((*node)->ch + c2id(s[i++]));
	}
	if (i == len) {
		return (Node*) ((*node)->ch + c2id(s[len]));
	}
}

/**
 * 寻找 Tree 中的叶节点
 */
TNode* Tree::findTNode(const string s, const int dep = 0) {
	TNode *node = root;
	TNode **next = NULL;
	int i = 0, len = s.length();
	assert(((dep == this->dep - 1) && (dep <= len)) || ((dep == 0) && (len == this->dep - 1)));
	if (0 != dep) {
		len = dep;
	}
	len--;
	while (i < len) {
		next = (TNode **) (node->ch + c2id(s[i++]));
		if (NULL == *next) {
			break;
		}
		node = *next;
	}
	while (i < len) {
		*next = new TNode();
		(*next)->f = node;
		node = *next;
		next = (TNode **) (node->ch + c2id(s[i++]));
	}
	return node;
}

/**
 * 根据索引树找到 Node 但并不创建 Node
 */
Node** Tree::findNode(const string s) {
	int i = 0, len = s.length();
	assert(len-- == this->dep);
	TNode *tnode = this->findTNode(s, len);
	return (Node**) (tnode->ch + c2id(s[len]));
}

string Path::toString() {
	string s = head->toString();
	for (auto i = edges.begin(); i != edges.end(); i++) {
		s.push_back(id2c(*i));
	}
	return s;
}

string Node::toString() {
	string s;
	TNode *node = idx;
	int i;
	while (NULL != idx) {
		for (i = 0; i < 4; i++) {
			if ((Node *)idx->ch[i] == this) {
				break;
			}
		}
		s.push_back(id2c(i));
		idx = idx->f;
	}
	reverse(s.begin(), s.end());
	return s;
}

void Graph::readDataset(vector<string> dt) {
	for (auto it = dt.begin(); it != dt.end(); it++) {
		readSeq(*it);
		readSeq(getReverseComplement(*it));
	}
}

void Graph::readSeq(string seq) {
#ifdef LOG
	cout << "readSeq()" << seq.length() << endl;
#endif
	int len = seq.length() - dep + 1;
	Node *node = NULL;
	for (int i = 0; i < len; i++) {
#ifdef LOG
	cout << i << endl;
#endif
		if (NULL == node || NULL == node->next) {
			node = addNode(seq.substr(i, dep));
		} else {
			node = addNode(node, seq[i + dep - 1]);
		}
	}
}

Node* Graph::addNode(std::string seq) {
#ifdef LOG
	cout << "addNode() " << seq << endl;
#endif
	assert(seq.length() == dep);
	TNode *node = t->findTNode(seq, seq.length() - 1);
	cout << "addNode -> finish findTNode " << node << endl;
	assert(node != NULL);
	Node *nodePtr = (Node *) node->ch[c2id(seq[seq.length() - 1])];
	cout << "test" << endl;
	if (nodePtr == NULL) {
		nodePtr = new Node(list.size());
		nodePtr->idx = node;
		list.push_back(nodePtr);
	}
	nodePtr->count++;
	cout << "OK" << endl;
	return nodePtr;
}

Node* Graph::addNode(Node *node, char c) {
	assert(node->next != NULL);
	Node **nodePtr = (Node**)(node->next->ch + c2id(c));
	if (NULL == *nodePtr) {
		*nodePtr = new Node(list.size());
		(*nodePtr)->idx = (TNode*)node->next;
		list.push_back(*nodePtr);
		count++;
	}
	(*nodePtr)->count++;
	return *nodePtr;
}

void Graph::deleteNode(Node *node) {
	node->idx = NULL;
	list[node->id] = NULL;
	delete node;
	count--;
}

void Graph::deletePath(Path *path) {
	Node *node = path->head, *next;
	for (auto i = path->edges.begin(); i != path->edges.end(); i++) {
		next = (Node*) (node->next->ch[*i]);
		this->deleteNode(node);
		node = next;
	}
	this->deleteNode(node);
}

void Graph::filter(int threshold) {
	for (auto it = list.begin(); it != list.end(); it++) {
		if (NULL != *it && (*it)->count < threshold) {
			deleteNode(*it);
		}
	}
}

void Graph::reset() {
	for (auto it = list.begin(); it != list.end(); it++) {
		if (NULL != *it) {
			(*it)->maxDepthNode = -1;
			(*it)->dep = 0;
		}
	}
	visitNum = 0;
	visit.assign(list.size(), false);
}

void Graph::clearBfs(bool clearVisit) {
	for (auto it = bfs.begin(); it != bfs.end(); it++) {
		if (clearVisit) {
			visit[(*it)->node->id] = false;
			visitNum--;
		}
		delete *it;
	}
	bfs.clear();
}

Path Graph::findPath(Node *node) {
	clearBfs(false);
	BfsNode *bnode = new BfsNode(), *head, *maxNode = NULL;
	size_t h = 0, t = 1, maxDep = 0;
	bnode->node = node;
	bfs.push_back(bnode);
	while (h < t) {
		head = bfs[h++];
		if (head->node->next != NULL) {
			for (int i = 0; i < 4; i++) {
				node = (Node*)head->node->next->ch[i];
				if (node != NULL && visit[node->id] == false) {
					bnode = new BfsNode();
					bnode->dep = head->dep + 1;
					bnode->edge = i;
					bnode->node = node;
					bnode->f = head;
					visit[node->id] = true;
					visitNum++;
					t++;
					bfs.push_back(bnode);
					if (bnode->dep > maxDep) {
						maxDep = bnode->dep;
						maxNode = bnode;
					}
				}
			}
		}
	}
	
	Path path;
	bnode = maxNode;
	path.tail = maxNode->node;
	while (NULL != bnode->f) {
		path.edges.push_back((char)bnode->edge);
		bnode = bnode->f;
	}
	path.head = bnode->node;
	reverse(path.edges.begin(), path.edges.end());
	return path;
}

Path Graph::findLongestPath() {
	Path path;
	int i, len = visit.size();
	while (path.length() < pathThreshold) {
		if (visitNum == count) {
			return path;
		}
		i = 0;
		while (i < len && (list[i] == NULL || visit[i])) {
			i++;
		}
		clearBfs(false);
		path = findPath(list[i]);
		clearBfs(true);
		path = findPath(path.tail);
	}
}
